#ifndef DUALLINKLIST_H
#define DUALLINKLIST_H

#include "List.h"
#include "Exception.h"

namespace DSLib
{

template <typename T>
class DualLinkList : public List<T>
{
protected:
	struct Node : public Object
	{
		T value;
		Node* pre;
		Node* next;
	};

	mutable struct : public Object
	{
		unsigned char reserverd[sizeof(T)];
		Node* pre;
		Node* next;
	}m_header;

	Node* position(int i) const
	{
		Node* current = reinterpret_cast<Node*>(&m_header);
		for (int p = 0; p < i; p++)
		{
			current = current->next;
		}
		return current;
	}

	virtual Node* create()
	{
		Node* ret = new Node();

		if (!ret)
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "alloc memory failed!");
		}
		
		return ret;	
	}

	virtual void destory(Node* pn)
	{
		if (pn != NULL)
		{
			delete pn;
			pn = NULL;
		}
	}

	int m_length;
	Node* m_current;
	int m_step;

public:
	DualLinkList()
	{
		m_header.pre = NULL;
		m_header.next = NULL;
		m_current = NULL;
		m_length = 0;
		m_step = 0;
	}

	virtual bool insert(int i, const T& e)
	{
		bool ret = ((0 <= i) && (i <= m_length));

		Node* node = create();

		if (!node)
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "alloc memory failed!");
		}

		Node* current = position(i);
		Node* next = current->next;

		node->value = e;

		node->next = next;
		current->next = node;

		if (current != reinterpret_cast<Node*>(&m_header))
		{
			node->pre = current;
		}
		else
		{
			node->pre = NULL;
		}

		if (next != NULL)
		{
			next->pre = node;
		}
		m_length++;

		return ret;
	}

	virtual bool insert(const T& e)
	{
		return insert(m_length, e);
	}

	virtual bool remove(int i)
	{
		bool ret = ((0 <= i) && (i < m_length));

		if (ret)
		{
			Node* current = position(i);
			Node* toDel = current->next;
			Node* next = toDel->next;

			if (m_current == toDel)
			{
				m_current = toDel->next;
			}

			current->next = next;

			if (next != NULL)
			{
				next->pre = toDel->pre;
			}

			m_length--;
			destory(toDel);
		}
		return ret;
	}

	virtual bool set(int i, const T& e)
	{
		bool ret = ((0 <= i) && (i < m_length));

		if (ret)
		{
			position(i)->next->value = e;
		}
		return ret;
	}

	virtual bool get(int i, T& e) const
	{
		bool ret = ((0 <= i) && (i < m_length));

		if (ret)
		{
			e = position(i)->next->value;
		}
		return ret;
	}

	virtual T get(int i) const
	{
		T v;

		if (get(i, v))
		{
			return v;
		}
		else
		{
			THROW_EXCEPTION(IndexOutOfBoundsException, "index i out of range!");
		}
	}

	virtual int find(const T& e) const
	{
		int ret = -1;

		Node* current = position(0)->next;
		for (int i = 0; i < m_length; i++)
		{
			if (current->value == e)
			{
				ret = i;
				break;
			}
			current = current->next;
		}
		return ret;
	}

	virtual int length() const
	{
		return m_length;
	}

	virtual void clear()
	{
		while (m_header.next)
		{
			remove(0);
		}
	}

	T& operator [] (int i)
	{
		if ((0 <= i) && (i < m_length))
		{
			return position(i)->next->value;
		}
		else
		{
			THROW_EXCEPTION(IndexOutOfBoundsException, "index i out of range!");
		}
	}

	T operator [] (int i) const
	{
		return const_cast<LinkList<T>&>(*this)[i];
	}

	virtual bool move(int i, int step = 1)
	{
		bool ret = ((0 <= i) && (i < m_length));
		ret = ret && (step >= 1);
		if (ret)
		{
			m_step = step;
			m_current = position(i)->next;
		}
		return ret;
	}

	virtual bool isEnd() const
	{
		return ((m_length == 0) || (m_current == NULL));
	}

	virtual T current() const
	{
		if (isEnd())
		{
			THROW_EXCEPTION(InvaildParameterException, "current node is Null");
		}

		return m_current->value;
	}

	virtual bool next()
	{
		int i = 0;
		while ((i < m_step) && !isEnd())
		{
			m_current = m_current->next;
			i++;
		}

		return (i == m_step);
	}

	virtual bool pre()
	{
		int i = 0;
		while ((i < m_step) && !isEnd())
		{
			m_current = m_current->pre;
			i++;
		}

		return (i == m_step);
	}

	~DualLinkList()
	{
		clear();
	}
};

}






#endif